package graph.unweighted.bfs.biPartitionDetection;

import java.util.ArrayList;
import java.util.Arrays;

import graph.unweighted.CandyGraph;
import queue.CandyLoopQueue;

/**
 * 
 * @Title: CandyBiPartittionDetection.java 
 * @Package graph.bfs.biPartitionDetection 
 * @Description: 使用BFS完成二分图检测：
 *                  记录顶点的颜色，可以被染成蓝色和绿色，没有遍历过的话默认是蓝色
 *                  如果在递归遍历的过程中，发现遍历过的顶点和当前顶点的颜色一样的话，
 *                  就表示不是一个二分图
 * @author CandyWall   
 * @date 2021年1月17日 上午10:56:07 
 * @version V1.0
 */
public class CandyBiPartitionDetection {
    private CandyGraph graph;
    private int[] colors;
    public CandyBiPartitionDetection(CandyGraph graph) {
        this.graph = graph;
        colors = new int[graph.getVertex_num()];
        for(int i = 0; i < graph.getVertex_num(); i++) {
            colors[i] = -1;
        }
        
    }
    
    /**
     * 检测是不是二分图
     * @return
     */
    public boolean isBiPartitionGraph() {
        for(int v = 0; v < graph.getVertex_num(); v++) {
            if(colors[v] == -1) {
                if(!bfs(v, 0)) {
                    return false;
                }
            }
        }
        return true;
    }
    
    /**
     * 获取二分图中的两个部分
     * @return
     */
    public ArrayList<Integer>[] getBiParts() {
        if(!isBiPartitionGraph()) {
            return null;
        }
        ArrayList<Integer>[] biParts = new ArrayList[2];
        biParts[0] = new ArrayList<>();
        biParts[1] = new ArrayList<>();
        for(int v = 0; v < graph.getVertex_num(); v++) {
            biParts[colors[v] == 0 ? 0 : 1].add(v);
        }
        return biParts;
    }
    
    private boolean bfs(int t, int color) {
        CandyLoopQueue<Integer> queue = new CandyLoopQueue<>();
        queue.enqueue(t);   // 第一个顶点入队
        colors[t] = color;  // 第一个顶点染色
        while(!queue.isEmpty()) {
            int v = queue.dequeue();
            for(int w : graph.adjacentVertexes(v)) {
                if(colors[w] == -1) {
                    queue.enqueue(w);
                    colors[w] = 1 - colors[v];
                } 
                // 如果被遍历过，颜色跟上一个顶点相同，就不是二分图
                else if(colors[w] == colors[v]) {
                    return false;
                }
            }
        }
        
        return true;
    }
    
    public static void main(String[] args) {
        CandyGraph graph1 = new CandyGraph("testData/graph/dfs/demo4/graph1.txt");
        CandyBiPartitionDetection biPartitionDetected1 = new CandyBiPartitionDetection(graph1);
        System.out.println("当前图是不是二分图：" + (biPartitionDetected1.isBiPartitionGraph() ? Arrays.toString(biPartitionDetected1.getBiParts()) : "当前图不是二分图"));
        CandyGraph graph2 = new CandyGraph("testData/graph/dfs/demo4/graph2.txt");
        CandyBiPartitionDetection biPartitionDetected2 = new CandyBiPartitionDetection(graph2);
        System.out.println("当前图是不是二分图：" + (biPartitionDetected2.isBiPartitionGraph() ? Arrays.toString(biPartitionDetected2.getBiParts()) : "当前图不是二分图"));

    }
}
